package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC880 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public String decodeAtIndex(String s, int k) {
            long[] len = new long[s.length()];
            len[0] = 1;
            int i = 1;
            while (k >= s.length() || len[i - 1] < k) {
                if (Character.isDigit(s.charAt(i))) {
                    //当前位是数字，需要扩展前一位的长度值
                    len[i] = len[i - 1] * Integer.parseInt(s.substring(i, i + 1));
                } else {
                    len[i] = len[i - 1] + 1;
                }

                if (k == len[i]) {
                    while (Character.isDigit(s.charAt(i))) --i;
                    //已经找到，直接返回
                    return s.substring(i, i + 1);
                }

                if (k < len[i]) {
                    //当前k可以缩短
                    k %= len[i - 1];
                    if (k == 0) {
                        --i;
                        while (Character.isDigit(s.charAt(i))) --i;
                        //已经找到，直接返回
                        return s.substring(i, i + 1);
                    }

                    break;
                }

                ++i;
            }

            while (k > 1) {
                for (int j = 1; j < i; j++) {
                    if (k == len[j]) {
                        while (Character.isDigit(s.charAt(j))) --j;
                        //已经找到，直接返回
                        return s.substring(j, j + 1);
                    }

                    if (k < len[j]) {
                        //当前k可以缩短
                        k %= len[j - 1];
                        if (k == 0) {
                            --j;
                            while (Character.isDigit(s.charAt(j))) --j;
                            //已经找到，直接返回
                            return s.substring(j, j + 1);
                        }

                        break;
                    }
                }
            }

            return s.substring(0, 1);
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.decodeAtIndex("leet2code3", 10));
        System.out.println(solution.decodeAtIndex("a2345678999999999999999", 6));
        System.out.println(solution.decodeAtIndex("vk6u5xhq9v", 554));
        System.out.println(solution.decodeAtIndex("ha22", 5));
        System.out.println(solution.decodeAtIndex("qgd883bxr7", 2458));
        System.out.println(solution.decodeAtIndex("n2f7x7bv4l", 110));
    }

    public static void main(String[] args) throws Exception {
        LC880 an = new LC880();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
